package com.lee.interview.sort;

import java.util.Random;

/**
 * 快速排序
 *
 */
public class QuickSort {
	
	public static void main(String[] args) {
		int num=10;
		int[] intArr = new int[num];
		Random random = new Random();
		for (int i = 0; i < intArr.length; i++) {
			intArr[i] = random.nextInt(num*10);
		}
		for (int i = 0; i < intArr.length; i++) {
			System.out.print(intArr[i]+"	");
		}
		System.out.println();
		
		QuickSort quickSort = new QuickSort();
		
		quickSort.sort(intArr,0, intArr.length-1);
		
		for (int i = 0; i < intArr.length; i++) {
			System.out.print(intArr[i]+"	");
		}
		System.out.println();
	}
	
	
	public  void sort(int[] intArr , int low , int high) {
		int left = low;
		int right = high;
		if (low < high) {
			int pivotValue = intArr[low];
			while (left<right) {
				// 从右边向左边扫描，找到小于基准值的数左移到 i 的位置
				while (left<right && intArr[right] > pivotValue) {
					right--;
				}
				if (left < right) {
					// while 退出时 intArr[j] <= pivotValue, 右边有小于pivotValue的值
					intArr[left] = intArr[right];		// right位置的数移动到 left 位置
					left++;
				}
				// 从左边向右边扫描，找到大于基准值的数右移到 right 的位置
				while (left<right && intArr[left] < pivotValue) {
					left++;
				}
				if (left<right) {
					// while 退出时 intArr[left] >= pivotValue, 左边有小于等于pivotValue的值
					intArr[right] = intArr[left];	// 将 left 位置的数据移动到 right 位置
					right--;
				}
				
			}
		
			intArr[left] = pivotValue;
			
			sort(intArr , low , left-1);
			
			sort(intArr ,left+1, high);
		}
		
	}
	
		
	
	
	
	
	
}
